package company.tree;

import java.util.*;

/**
 * 113. 路径总和 II
 * 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
 * <p>
 * 叶子节点 是指没有子节点的节点。
 * 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
 * 输出：[[5,4,11,2],[5,8,4,5]]
 * <p>
 * 输入：root = [1,2,3], targetSum = 5
 * 输出：[]
 * <p>
 * <p>
 * 输入：root = [1,2], targetSum = 0
 * 输出：[]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/path-sum-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 分析：
 * 1、忽略了节点可以重复，所以不能用map来当前节点和当前节点路径关系
 * 2、但是可以用map存储子节点和父节点关系
 * 2、这时候可以考虑用回溯法找父子关系，同时记得要顺序反转，因为先便利路径是子节点，
 *
 */
public class PathSumTwo113 {
    static List<List<Integer>> ret = new LinkedList<List<Integer>>();
    static Map<TreeNode, TreeNode> map = new HashMap<TreeNode, TreeNode>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] input = sc.nextLine().split("\\s+");
        String[] node = input[0].replace("[", "").
                replace("]", "").replace("\\s+", "").split(",");
        input[1].replace("\\s+", "");
        TreeNode treeNode = null;
        treeNode = packTree(treeNode, node);
        System.out.println(pathSum(treeNode, Integer.parseInt(input[1])));
    }

    private static TreeNode packTree(TreeNode treeNode, String[] node) {
        // 根节点
        if (treeNode == null) {
            treeNode = new TreeNode(Integer.parseInt(node[0]));
        }
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(treeNode);
        int idx = 0;
        int len = node.length;
        while (++idx < len) {
            // 取出父节点
            TreeNode poll = deque.poll();

            // 处理左子树
            if (poll.getLeft() == null) {
                if (!node[idx].equals("null")) {
                    TreeNode left = new TreeNode(Integer.parseInt(node[idx]));
                    poll.setLeft(left);
                    deque.offer(left);
                }
            }
            ++idx;

            // 处理右子树
            if (idx < len && poll.getRight() == null) {
                if (!node[idx].equals("null")) {
                    TreeNode right = new TreeNode(Integer.parseInt(node[idx]));
                    poll.setRight(right);
                    deque.offer(right);
                }
            }
        }
        return treeNode;
    }

    private static List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return ret;
        }

        Queue<TreeNode> queueNode = new LinkedList<TreeNode>();
        Queue<Integer> queueSum = new LinkedList<Integer>();
        queueNode.offer(root);
        queueSum.offer(0);

        while (!queueNode.isEmpty()) {
            TreeNode node = queueNode.poll();
            int rec = queueSum.poll() + node.getValue();

            if (node.getLeft() == null && node.getRight() == null) {
                if (rec == targetSum) {
                    getPath(node);
                }
            } else {
                if (node.getLeft()!= null) {
                    map.put(node.getLeft(), node);
                    queueNode.offer(node.getLeft());
                    queueSum.offer(rec);
                }
                if (node.getRight() != null) {
                    map.put(node.getRight(), node);
                    queueNode.offer(node.getRight());
                    queueSum.offer(rec);
                }
            }
        }

        return ret;
    }

    public static void getPath(TreeNode node) {
        List<Integer> temp = new LinkedList<Integer>();
        while (node != null) {
            temp.add(node.getValue());
            node = map.get(node);
        }
        Collections.reverse(temp);
        ret.add(new LinkedList<Integer>(temp));
    }
}